package com.example.zzy.zzytest.data.structure.stack.polandnotation;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 中缀转后缀
 * 1.初始化res栈和op栈
 * 2.扫描表达式，遇到num则push res栈
 * 3.遇到op，比较其与op栈顶运算符的优先级
 * 3.1如果op栈为空，或栈顶为左括号，则当前操作符入op栈
 * 3.2如果op栈不为空，当前操作符比op栈顶运算符优先级高，则当前op入栈
 * 3.3否则将op栈顶运算符弹出，入res栈，然后在转到3.1，比较当前op和新的栈顶op
 * 4.遇到括号
 * 4.1左括号直接入op栈
 * 4.2右括号，依次弹出op栈的操作符，入res栈，直到遇到左括号，然后这一对括号丢弃
 * 5.继续扫描表达式到达最后
 * 6.将op栈操作符依次弹出，压入res
 * 7.将res栈元素依次弹出即完成
 */
public class PolandConverse {
    public static void main(String[] args) {
        String calcText = "1+((2+3)*4)-5";
        //支持多位数
        //String calcText = "12+((34+56)*78)-90";
        List<String> calcArr = toInfixExpList(calcText);
        String res = converse(calcArr);
        System.out.println(res);

    }

    public static String converse(List<String> calcArr) {
        Stack<String> opStack = new Stack<>();
        Stack<String> res = new Stack<>();

        for (String s : calcArr) {
            if (s.matches("\\d+")) {
                res.push(s);

            } else if ("(".equals(s)) {
                opStack.push(s);

            } else if (")".equals(s)) {
                while (!"(".equals(opStack.peek())) {
                    res.push(opStack.pop());
                }
                opStack.pop();

            } else {
                if (opStack.empty() || "(".equals(opStack.peek())) {
                    opStack.push(s);
                    continue;
                }
                if (!opStack.empty() && (priority(s) <= priority(opStack.peek()))) {
                    while (!opStack.empty() && (priority(s) <= priority(opStack.peek()))) {
                        res.push(opStack.pop());
                    }
                }
                opStack.push(s);

            }
        }

        while (!opStack.empty()) {
            res.push(opStack.pop());
        }

        StringBuilder sb = new StringBuilder();
        while (!res.empty()) {
            sb.append(res.pop());
        }

        return sb.reverse().toString();
    }

    /**
     * 将中缀表达式String放到List里
     *
     * @param s
     * @return
     */
    public static List<String> toInfixExpList(String s) {
        List<String> res = new ArrayList<>();
        int index = 0;      //index用来扫描
        char c;             //用来接收index

        while (index < s.length()) {

            if ((c = s.charAt(index)) < 48 || (c = s.charAt(index)) > 57) {
                //c为非数字
                res.add(c + "");
                index++;
            } else {
                String cat = "";
                while (index < s.length() && ((c = s.charAt(index)) >= 48 && (c = s.charAt(index)) <= 57)) {
                    cat += c;
                    index++;
                }
                res.add(cat);
            }
        }
        return res;
    }

    /**
     * 得出操作符的优先级
     *
     * @param c
     * @return
     */
    public static int priority(String c) {
        if (c == "*" || c == "/") {
            return 1;
        } else if (c == "+" || c == "-") {
            return 0;
        } else {
            return -1;
        }
    }
}
